package com.platform.modules.alg.alglib.hdu5002;

/**
 * @className: Hdu5002
 * @description: http://hzwer.com/5540.html
 * @date: 2022/11/17
 * @author: chengqiuming
 */
public class Hdu5002 {
    private int inf = 0x3f3f3f3f;
    private int N = 100005;

    int n, m, top;
    int c[][] = new int[N][2];
    int fa[] = new int[N];
    int v[] = new int[N];
    int st[] = new int[N];
    int mx1[] = new int[N]; // 最大值
    int mx2[] = new int[N]; // 次大值
    int c1[] = new int[N];  // 两者的重复次数
    int c2[] = new int[N];  // 子树大小
    int size[] = new int[N]; // 子树大小
    int ta[] = new int[N]; // 增加懒标记
    int tc[] = new int[N]; // 修改懒标记
    int rev[] = new int[N]; // 反转懒标记

    public String output = "";

    // 统计 x 的子树中最大、次大值和重复次数，当前节点值为 val,其重复次数为 c
    void cnt(int x, int val, int c) {
        if (val > mx1[x]) {
            mx2[x] = mx1[x];
            mx1[x] = val;
            c2[x] = c1[x];
            c1[x] = c;
        } else if (val == mx1[x]) {
            c1[x] += c;
        } else if (val > mx2[x]) {
            mx2[x] = val;
            c2[x] = c;
        } else if (val == mx2[x]) {
            c2[x] += c;
        }
    }

    // y 为根的子树上所有节点改为 val
    void change(int y, int val) {
        mx1[y] = val;
        v[y] = val;
        c1[y] = size[y];
        mx2[y] = -inf;
        c2[y] = 0;
        tc[y] = val;
        if (ta[y] != 0) ta[y] = 0;
    }

    // y 为根的子树上所有节点加 val
    void addval(int y, int val) {
        ta[y] += val;
        mx1[y] += val;
        v[y] += val;
        if (mx2[y] != -inf) mx2[y] += val;
    }

    void update(int x) {
        int l = c[x][0], r = c[x][1];
        mx1[x] = mx2[x] = -inf;
        c1[x] = c2[x] = 0;
        cnt(x, v[x], 1);
        if (l > 0) {
            cnt(x, mx1[l], c1[l]);
            cnt(x, mx2[l], c2[l]);
        }
        if (r > 0) {
            cnt(x, mx1[r], c1[r]);
            cnt(x, mx2[r], c2[r]);
        }
        size[x] = size[l] + size[r] + 1;
    }

    void pushdown(int x) {
        int l = c[x][0], r = c[x][1];
        if (rev[x] == 1) {//反转
            rev[x] ^= 1;
            rev[l] ^= 1;
            rev[r] ^= 1;
            // 交换两者的值，不要写l,r
            int temp = c[x][0];
            c[x][0] = c[x][1];
            c[x][1] = temp;
        }
        if (tc[x] != -inf) {//修改
            if (l > 0) change(l, tc[x]);
            if (r > 0) change(r, tc[x]);
            tc[x] = -inf;
        }
        if (ta[x] != 0) {//增加
            if (l > 0) addval(l, ta[x]);
            if (r > 0) addval(r, ta[x]);
            ta[x] = 0;
        }
    }

    boolean isroot(int x) {
        return c[fa[x]][0] != x && c[fa[x]][1] != x;
    }

    void rotate(int x) {
        int y = fa[x], z = fa[y], l, r;
        if (c[y][0] == x) l = 0;
        else l = 1;
        r = l ^ 1;
        if (!isroot(y)) {
            if (c[z][0] == y) c[z][0] = x;
            else c[z][1] = x;
        }
        fa[x] = z;
        fa[y] = x;
        fa[c[x][r]] = y;
        c[y][l] = c[x][r];
        c[x][r] = y;
        update(y);
        update(x);
    }

    void splay(int x) {
        top = 0;
        st[++top] = x;
        for (int i = x; !isroot(i); i = fa[i])
            st[++top] = fa[i];
        while (top > 0) pushdown(st[top--]);
        while (!isroot(x)) {
            int y = fa[x], z = fa[y];
            if (!isroot(y)) {
                if (c[y][0] == x ^ c[z][0] == y) {
                    rotate(x);
                } else {
                    rotate(y);
                }
            }
            rotate(x);
        }
    }

    void access(int x) {
        for (int t = 0; x > 0; t = x, x = fa[x]) {
            splay(x);
            c[x][1] = t;
            update(x);
        }
    }

    void makeroot(int x) {
        access(x);
        splay(x);
        rev[x] ^= 1;
    }

    void link(int x, int y) {
        makeroot(x);
        fa[x] = y;
    }

    void split(int x, int y) {
        makeroot(x);
        access(y);
        splay(y);
    }

    void cut(int x, int y) {
        split(x, y);
        c[y][0] = fa[c[y][0]] = 0;
        update(y);
    }

    int findroot(int x) {
        access(x);
        splay(x);
        while (c[x][0] > 0) x = c[x][0];
        return x;
    }

    void query(int x, int y) {
        if (c1[y] == size[y]) {
            output += "ALL SAME";
        } else {
            output += mx2[y] + " " + c2[y] + "\n";
        }
    }


    public String cal(String input) {
        int opt, x, y, a, b, d;
        String[] line = input.split("\n");

        String[] num = line[0].split(" ");
        n = Integer.parseInt(num[0]);
        m = Integer.parseInt(num[1]);
        String[] wage = line[1].split(" ");
        for (int i = 1; i <= n; i++) {
            v[i] = Integer.parseInt(wage[i - 1]);
        }

        for (int i = 1; i <= n; i++) {
            mx1[i] = v[i];
            c1[i] = 1;
            mx2[i] = -inf;
            c2[i] = 0;
            size[i] = 1;
        }
        for (int i = 1; i <= n; i++) {
            fa[i] = c[i][0] = c[i][1] = 0;
            ta[i] = rev[i] = 0;
            tc[i] = -inf;
        }
        for (int i = 1; i < n; i++) {
            String[] edge = line[i + 1].split(" ");
            x = Integer.parseInt(edge[0]);
            y = Integer.parseInt(edge[1]);
            link(x, y);
        }
        int count = 1;
        while (m-- > 0) {
            String[] query = line[n + count++].split(" ");
            opt = Integer.parseInt(query[0]);
            if (opt == 1) {
                x = Integer.parseInt(query[1]);
                y = Integer.parseInt(query[2]);
                a = Integer.parseInt(query[3]);
                b = Integer.parseInt(query[4]);
                cut(x, y);
                link(a, b);
            } else if (opt == 2) {
                a = Integer.parseInt(query[1]);
                b = Integer.parseInt(query[2]);
                x = Integer.parseInt(query[3]);
                split(a, b);
                change(b, x);
            } else if (opt == 3) {
                a = Integer.parseInt(query[1]);
                b = Integer.parseInt(query[2]);
                d = Integer.parseInt(query[3]);
                split(a, b);
                addval(b, d);
            } else {
                a = Integer.parseInt(query[1]);
                b = Integer.parseInt(query[2]);
                split(a, b);
                query(a, b);
            }
        }

        return output;
    }
}
